package basic.study.leetcode;

import java.nio.IntBuffer;
import java.util.Stack;

/**
 * @ClassName Mid114
 * @Description 二叉树展开为链表
 * @Company inspur
 * @Author Kevin
 * @Date 2020/6/26 10:36
 * @Version 1.0
 */
public class Mid114 {
    /**
     * 前序展开,遍历
     */
    class Solution {
        public void flatten(TreeNode root) {
            while (root!= null) {
                if (root.left == null) {
                    root = root.right;
                } else {
                    //找到左子树下最右节点
                    TreeNode pre = root.left;
                    while (pre.right != null) {
                        pre = pre.right;
                    }
                    //将右子树插入左子树后
                    pre.right = root.right;
                    //替换原右子树为左子树
                    root.right = root.left;
                    root.left = null;
                    //考虑下一节点
                    root = root.right;
                }
            }
        }
    }

    class Solution1 {
        public void flatten(TreeNode root) {
            Stack<TreeNode> toVisit = new Stack<>();
            TreeNode cur = root;
            TreeNode pre= null;

            while (cur!= null || !toVisit.isEmpty()) {
                while (cur != null) {
                    toVisit.push(cur); // 添加根节点
                    cur = cur.right;// 递归添加右节点
                }
                cur = toVisit.peek(); // 已经访问到最右的节点了
                // 在不存在左节点或者右节点已经访问过的情况下，访问根节点
                if (cur.left == null || cur.left == pre) {
                    toVisit.pop();

                    cur.right = pre;
                    cur.left = null;

                    pre = cur;
                    cur = null;
                } else {
                    cur = cur.left;// 左节点还没有访问过就先访问左节点
                }
            }
        }
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
